\documentclass{llncs}

\usepackage[utf8]{inputenc}
\input{DeclareUnicodeCharacter}
\usepackage{color}
\definecolor{shadecolor}{rgb}{.9,.9,1} 
\usepackage{url}
\usepackage{amsmath} 
\usepackage{amssymb}
\usepackage{picinpar}

\usepackage{tikz}
\usetikzlibrary{matrix,arrows}
\usepackage{pgfplots}
\usetikzlibrary{plotmarks}
%\usetikzlibrary{positioning}
%\usetikzlibrary{shapes,shadows,arrows}
\usetikzlibrary{calc}
%\pgfplotsset{compat=1.3}
%\pgfdeclarelayer{background}
%\pgfdeclarelayer{foreground}
%\pgfsetlayers{background,main,foreground}

\newcommand{\LPBs}{\mathit{LPBs}}
\newcommand{\sd}[1]{#1}%{\colorbox{shadecolor}{#1}}
\newcommand{\ld}[1]{\raisebox{-1ex}[0cm][0cm]{\sd{#1}}}
\newcommand{\ud}[1]{\raisebox{1ex}[0cm][0cm]{\sd{#1}}}
\newcommand{\ub}[1]{\raisebox{1ex}[0cm][0cm]{#1}}
\newcommand{\repeatlabel}[1]{\label{#1}}
\newcommand{\defining}[1]{\textbf{#1}}
\newcommand{\bool}{\mathit{Bool}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\false}{\mathit{false}}
\newcommand{\true}{\mathit{true}}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\integ}{\mathbb{Z}}
\newcommand{\onetom}{{[1..m]}}
\newcommand{\onetol}{{[1..l]}} 
\newcommand{\zerotol}{{[0..l]}}   
\newcommand{\iso}{\mathfrak{I}^\leq}
\newcommand{\isop}{\mathfrak{I}^=}
\newcommand{\ineq}{\mathit{Ineq}^\leq}
\newcommand{\ineqp}{\mathit{Ineqp}^=}
\newcommand{\mono}{\mathfrak{M}^\leq}
\newcommand{\monop}{\mathfrak{M}^=}
\newcommand{\coeffSum}[2]{\sum_{i=#1}^{#2}a_ix_i}
\newcommand{\coeffSumPrime}[2]{\sum_{i=#1}^{#2}a'_ix_i}
\newcommand{\ms}[1]{\{\hspace{-0.2em}[#1]\hspace{-0.2em}\}}
\newcommand{\OP}{\mathit{OP}}
\newcommand{\Cut}[3]{\mathit{S}(#1,#2,#3)}
\newcommand{\CutT}[2]{\mathit{S}(\cdot,#1,#2)}
\newcommand{\mint}{s}
\newcommand{\maxt}{b}
\newcommand{\threshold}[2]{(#1,#2]}
\newcommand{\LPBT}[2]{}%\mathit{I}(#1,#2)\equiv}

%For pseudocode
\newcommand{\uc}{\mathit{uc}}
\newcommand{\lc}{\mathit{lc}}
\newcommand{\parent}{\mathit{parent}}
\newcommand{\col}{\mathit{col}}
\newcommand{\pat}{\mathit{path}}
\newcommand{\MU}{\mathit{MU}}
\newcommand{\ML}{\mathit{ML}}
\newcommand{\NU}{\mathit{NU}}
\newcommand{\NL}{\mathit{NL}}
\newcommand{\MUs}{\mathit{MUs}}
\newcommand{\MLb}{\mathit{MLb}}
\newcommand{\NUb}{\mathit{NUb}}
\newcommand{\NLs}{\mathit{NLs}}
\newcommand{\MUU}{\mathit{MUU}}
\newcommand{\MLU}{\mathit{MLU}}
\newcommand{\NUU}{\mathit{NUU}}
\newcommand{\NLU}{\mathit{NLU}}
\newcommand{\MUL}{\mathit{MUL}}
\newcommand{\MLL}{\mathit{MLL}}
\newcommand{\NUL}{\mathit{NUL}}
\newcommand{\NLL}{\mathit{NLL}}
\newcommand{\jump}{\mathit{jump}}
\newcommand{\repair}{\mathrm{repair}}


%\newtheorem{theorem}{Theorem}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{corollary}[theorem]{Corollary}

\spnewtheorem{rmtheorem}[theorem]{Theorem}{\bfseries}{\rm} 
\spnewtheorem{rmlemma}[theorem]{Lemma}{\bfseries}{\rm} 
\spnewtheorem{rmcorollary}[theorem]{Corollary}{\bfseries}{\rm} 
\spnewtheorem{rmproposition}[theorem]{Proposition}{\bfseries}{\rm} 
\spnewtheorem{rmdefinition}[theorem]{Definition}{\bfseries}{\rm} 
\spnewtheorem{rmexample}[theorem]{Example}{\it}{\rm} 

\begin{document}

\title{A Pretty Complete Combinatorial Algorithm for the
Threshold Synthesis Problem}


\author{Christian Schilling\inst{1} \and Jan-Georg Smaus\inst{2} and Fabian Wenzelmann\inst{1}}

\institute{
Institut f\"ur Informatik, Universit\"at Freiburg, Germany
\and 
IRIT, Universit\'e de Toulouse, France, \texttt{smaus@irit.fr}
}

\maketitle

%\vspace*{-5cm}


% A category with the (minimum) three required fields
%\category{G.2.1}{Discrete Mathematics}{Combinatorics}[Combinatorial
%algorithms]
%\category{G.1.6}{Numerical analysis}{Optimization}[Integer
%programming, linear programming]
%\category{E.1}{Data structures}{Graphs and networks, trees}
%\category{G.1.0}{Numerical analysis}{General}[Interval arithmetic]
%\category{G.1.3}{Numerical analysis}{Numerical linear algebra}[Linear systems]


%\terms{Algorithms, experimentation, theory}

%\keywords{Boolean functions, threshold logic, linearly separable functions}

%\input{macros}

\bibliographystyle{plain}

%\pagestyle{plain}



\section{Introduction}\label{intro-sec}
A \emph{linear pseudo-Boolean constraint} (LPB)
\cite{CraHam11,%AloRamMarSak02,Bar93,
ChaKue03,%seems important because at least they actually use the name "LPB"
DixGin-KER00%seems rich in applications. AI + operations research
%,Dix04,
%FraHer03,FraHer06
} 
is an expression of the form
$a_1\ell_1+\ldots+a_m\ell_m\geq d$. Here each $\ell_i$ is a \emph{literal} of
the form $x_i$ or $1-x_i$.
An LPB can be used to represent a 
Boolean %\footnote{Whenever we say ``function'' we mean ``Boolean function''.}
function; e.g.~$2x_1+x_2+x_3\geq2$ represents the 
same  function as the propositional formula 
$x_1\lor(x_2\land x_3)$% 
%(we identify propositional formulae with  functions)
. 

Functions that can be represented by a single LPB are called
\emph{threshold functions}. %\footnote{For applications consider
%  \cite{GowVru08}.}  
The problem of finding the LPB for a threshold
function given as disjunctive normal form (DNF) is called
\emph{threshold synthesis problem}.  The reference on Boolean
functions \cite{CraHam11} formulates the research challenge of
recognising threshold functions through an entirely combinatorial
procedure. In fact, such a procedure had been proposed in
\cite{CoaLew61,CoaKirLew62} and was later reinvented by us \cite{Sma-CPAIOR07}.  
In this paper, we report on an implementation of this procedure for
which we have run experiments for up to $m=22$. It 
can solve the biggest problems in a couple of seconds.

There is another procedure solving this problem using linear
programming \cite{CraHam11}, which we also implemented and compared to
the combinatorial one. 

\section{Preliminaries}\label{prelim-sec}
An \defining{$m$-dimensional Boolean function} $f$ is a function 
$\bool^m\to\bool$. 
A \defining{linear pseudo-Boolean constraint} (LPB)
is an inequality of the form
\begin{equation}\label{LPB-eq}
a_1\ell_1+\ldots+a_m\ell_m\geq d
\qquad a_i\in\nat, d\in\integ, \ell_i\in\{x_i,1-x_i\}.
\end{equation}
We call the $a_i$ \defining{coefficients} and $d$ the
\defining{threshold}.
A \defining{DNF} is a 
formula of the form $c_1\lor\ldots\lor c_n$
where each \defining{clause} $c_j$ is a conjunction of literals. 

It is easy to see that an LPB can only represent \emph{monotone}
functions, i.e., functions represented by a DNF where each variable
occurs in only one polarity.  Without loss of generality, we assume
that this polarity is positive.




\section{The Combinatorial Algorithm}\label{encoding-sec}
For space reasons, we do not give a general definition of our
algorithm but rather illustrate it using a running example:  
$\phi\equiv$\\
$(x_1\land x_2)\lor(x_1\land x_3)\lor(x_1\land x_4)\lor(x_1\land x_5)\lor(x_2\land x_3)\lor
(x_2\land x_4)\lor(x_3\land x_4\land x_5)$. 

Before we start, it should be noted that the basic procedure we
describe here is not complete. Up to $m=7$, it always succeeds; up to
$m=14$, it fails on less than 1\% of the threshold functions, while
this rate rises up to 18.3\% for $m=22$. The issue of completeness is
very complicated, and \cite{CoaLew61} devote 23 pages to it!

For some DNFs, it is possible to establish a complete order $\succeq$ on the
variables which has the following meaning: $x_i\succeq x_j$ iff starting
from any given input tuple $X^* \in \bool^m$, setting $x_i^*$ to true is
more likely to make the DNF true than setting $x_j^*$ to true. There is a
lemma stating that $\succeq$ must be respected by any LPB (if there is one!)
representing the DNF, i.e., $x_i\succeq x_j$ implies $a_i\geq a_j$.
For $\phi$, it is the case that 
$x_1\succeq\ldots\succeq x_5$ and so if we find a solution, then $a_1\geq\ldots\geq a_5$. 

Now there is a theorem stating that the problem can be tackled using a
special kind of recursion. In $\phi$, we can distinguish the clauses that
contain $x_1$ and the ones that do not. This is illustrated in Figure
\ref{op-cont-figure}. In the leftmost column (column 0), we have $\phi$.
In column 1, we have two smaller DNFs: on top the clauses of $\phi$ that
do not contain $x_1$, and on bottom the clauses of $\phi$ that contain
$x_1$, but with those occurrences of $x_1$ removed.  We say that we
\emph{split away} $x_1$ from $\phi$, and we call the two formulas we
obtain the \emph{upper} and \emph{lower} successor of $\phi$.  We thus have two smaller
subproblems, and the theorem says that we must find solutions to these
subproblems that agree on the coefficients $a_2,\ldots,a_5$ (but differ on the
threshold, of course).

\begin{figure*}[t]
\begin{center}
\begin{tabular}{l|l|l|l|l|l}
&                      &                      &                             & \ld{$\false$} & $\false$\\
&                    & \ld{$x_3\land x_4\land x_5$}      &\sd{$\false$}      & \ld{$\false$} & $\false$ \\
&$(x_2\land x_3)\lor$         &                      & \sd{$x_4\land x_5$}    &  \ld{$x_5$} & $\false$ \\
&$(x_2\land x_4)\lor$          &                      &                    &                         &  $\true$\\\cline{4-6}
$(x_1\land x_2)\lor(x_1\land x_3)$&$(x_3\land x_4\land x_5)$      &                 & \ld{$x_4$}      & $\false$ & \\
$\lor(x_1\land x_4)\lor(x_1\land x_5)$&                     &    $x_3\lor x_4$      & \ld{$\true$}       & $\true$ & \\
$\lor(x_2\land x_3)\lor(x_2\land x_4)$&     &     &            & $\true$ & \\\cline{3-6}
&&&&&\\[-2.7ex]                   
$\lor(x_3\land x_4\land x_5)$&                     &                    &                          & \ld{$x_5$} &$\false$ \\
&                     &                    & \sd{$x_4\lor x_5$}               & \ld{$\true$} &$\true$ \\
&$x_2\lor x_3\lor x_4\lor x_5$    &\ud{$x_3\lor x_4\lor x_5$}     & \sd{$\true$}       & \ld{$\true$} &$\true$ \\
&                     &\ud{$\true$}& \sd{$\true$}        & \ld{$\true$} & $\true$\\
&                     &                   &                                &                    &$\true$
\vspace{2ex}
\end{tabular}\caption{The recursive subproblems for $\phi$ \label{op-cont-figure}}
\end{center}
\end{figure*}

Similarly, we can split away $x_2$ from each DNF in column 1,
giving the four formulae of column 2. Observe that the only
clause in $x_2\lor x_3\lor x_4\lor x_5$ containing $x_2$ is $x_2$, and if
we remove $x_2$ from it, we are left with the empty
conjunction which is $\true$; hence we have $\true$ as lowermost
formula in column 2. 

We continue by splitting away $x_3$ from the DNFs in column 2. From
now on, it is no more the case that the number of DNFs doubles in each
step. In fact, thanks to the symmetry of the variables in $x_2\lor x_3\lor
x_4\lor x_5$, it happens that the lower successor of $x_3\lor x_4\lor x_5$ 
coincides with the upper successor of $\true$, namely $\true$. Due to
this fact, Figure \ref{op-cont-figure} is \emph{not quite} a tree, as
some nodes are shared. 

Reducing the size of the datastructure by exploiting symmetries within
the DNF is obviously good for the space complexity of our procedure,
and is an advantage of \cite{Sma-CPAIOR07} compared to
\cite{CoaLew61,CoaKirLew62}. In fact, \cite{CoaKirLew62} does consider
symmetries but only at the global level: in $\phi$, the variables $x_3$
and $x_4$ are symmetric, but in the subproblems, there are more
symmetries.

Observe also that $x_3\land x_4\land x_5$ has no clause not containing $x_3$,
and thus we get the empty DNF ($=\false$) as upper successor. 

This process is continued until we finally obtain the ``tree'' in
Figure \ref{op-cont-figure}. As leaves, it has 12 (rather than $2^5=32$
as a construction not exploiting any symmetries would give)
occurrences of $\true$ or $\false$. 
\label{only12}


We now generalise LPBs by recording to what extent
thresholds can be shifted without changing the meaning. 

\begin{rmdefinition}
Given an LPB $I\equiv \coeffSum{1}{m}\geq d$, we call 
$\mint$ the \defining{minimum threshold} of $I$ if 
$\mint$ is the smallest number (possibly $-\infty$) such that for any 
$\mint'\in (\mint,d]$,  the LPB
$\coeffSum{1}{m}\geq \mint'$ represents the same  function as $I$. 
We call $\maxt$ the \defining{maximum threshold} if $\maxt$ is the 
biggest number (possibly $\infty$) such that 
$\coeffSum{1}{m}\geq \maxt$ represents the same  function as $I$.
We denote by $\coeffSum{1}{m}\geq \threshold{\mint}{\maxt}$ any 
LPB with minimum threshold $\mint$ and maximum threshold
$\maxt$.
\end{rmdefinition}


Now that we have constructed the ``tree'' containing trivial
subproblems as leaves, we must work back from the right to the left: we first find LPBs for the
formulae in the rightmost column, which have $0$ variables and hence we must
determine $0$ coefficients. Next to the left, we have formulae that contain (at
most) $x_5$, and we determine LPBs representing these, where we use the same
$a_5$ for all formulae! Then we determine $a_4$, and so forth. 

\begin{figure*}[t]
\begin{center}
\begin{tabular}{r|r|r|r|r|r}
%$4x_1+3x_2+$&&&&&\\
%$2x_3+2x_4+$&$3x_2+2x_3$    & $2x_3+$               &                             &                          &  \\
%$x_5\geq\ldots$& $2x_4+x_5\geq\ldots$ & $2x_4+x_5\geq\ldots$             & $2x_4+x_5\geq\ldots$                & $x_5\geq\ldots$                   & $\sum_{i=6}^5a_ix_i\geq\ldots$\\\hline\hline  
$4x_1+3x_2+$&     $3x_2+$  &                      &                          &                    &              \\
$2x_3+2x_4+$&$2x_3+2x_4+$  & $2x_3+2x_4+$            &        $2x_4+$            &                      & $\sum_{i=6}^5a_ix_i$ \\
$x_5\geq\ldots$&$x_5\geq\ldots$        & $x_5\geq\ldots$               &  $x_5\geq\ldots$               &   $x_5\geq\ldots$             &  $\geq\ldots$    \\\hline\hline
&                      &                      &                             & \ld{$\LPBT{x_{3..4}}{0}\threshold{1}{\infty}$} & $\LPBT{x_{3..5}}{0}\threshold{0}{\infty}$\\
&$\LPBT{x_1}{0}$        & $\LPBT{x_2}{0}$      & \sd{$\LPBT{x_{3}}{0}\threshold{3}{\infty}$}     & \ld{$\LPBT{x_{3..4}}{1}\threshold{1}{\infty}$} & $\LPBT{x_{3..5}}{1}\threshold{0}{\infty}$ \\
&                     & \ub{$\threshold{4}{5}$}         & \sd{$\LPBT{x_{3}}{1}\threshold{2}{3}$}      &  \ld{$\LPBT{x_{3..4}}{2}\threshold{0}{1}$} & $\LPBT{x_{3..5}}{2}\threshold{0}{\infty}$ \\
&$\threshold{4}{5}$              &                      &                                 &                         &  $\LPBT{x_{3..5}}{3}\threshold{-\infty}{0}$\\\cline{4-6}
&                     & $\LPBT{x_2}{1}$    & \ld{$\LPBT{x_{3}}{0}\threshold{1}{2}$}      & $\LPBT{x_{3..4}}{0}\threshold{1}{\infty}$ & \\
&                     &    $\threshold{1}{2}$         & \ld{$\LPBT{x_{3}}{1}\threshold{-\infty}{0}$}       & $\LPBT{x_{3..4}}{1}\threshold{-\infty}{0}$ & \\
\raisebox{-1ex}[0cm][0cm]{$\threshold{4}{5}$}&     &     &                                 & $\LPBT{x_{3..4}}{2}\threshold{-\infty}{0}$ & \\\cline{3-6}
&&&&&\\[-2.7ex]                   
&                     &                    &                                 & \ld{$\LPBT{x_{3..4}}{0}\threshold{0}{1}$} &$\LPBT{x_{3..5}}{0}\threshold{0}{\infty}$ \\
&$\LPBT{x_1}{1}$       &                    &\sd{$\LPBT{x_{3}}{0}\threshold{0}{1}$}      & \ld{$\LPBT{x_{3..4}}{1}\threshold{-\infty}{0}$} &$\LPBT{x_{3..5}}{1}\threshold{-\infty}{0}$ \\
&$\threshold{0}{1}$              &\ud{$\LPBT{x_2}{0}\threshold{0}{1}$}& \sd{$\LPBT{x_{3}}{1}\threshold{-\infty}{0}$}       & \ld{$\LPBT{x_{3..4}}{2}\threshold{-\infty}{0}$} &$\LPBT{x_{3..5}}{2}\threshold{-\infty}{0}$ \\
&                     &\ud{$\LPBT{x_2}{1}\threshold{-\infty}{0}$}& \sd{$\LPBT{x_{3}}{2}\threshold{-\infty}{0}$}   & \ld{$\LPBT{x_{3..4}}{3}\threshold{-\infty}{0}$} & $\LPBT{x_{3..5}}{3}\threshold{-\infty}{0}$\\
&                     &                   &                                &                    &$\LPBT{x_{3..5}}{4}\threshold{-\infty}{0}$
\end{tabular}
\end{center}
\vspace{1ex}
\caption{LPBs for $\phi$ and its the subproblems \label{op-cont-thresh-figure}}
\end{figure*}

Instead of giving the according theorem, 
we stick to our example: Figure \ref{op-cont-thresh-figure} is arranged
in correspondence to Figure \ref{op-cont-figure} and shows LPBs
for all subproblems.  In the top line we give the l.h.s.~of the LPBs,
which is the same for each LPB in a column. In the actual ``tree'', we
list the minimum and maximum threshold of each formula. 
We show how to construct this ``tree''.





Observe first that $\sum_{i=6}^5a_ix_i\geq\threshold{-\infty}{0}$ and
$\sum_{i=6}^5a_ix_i\geq\threshold{0}{\infty}$ are LPB representations (with empty
sum as l.h.s.) for $\true$
and $\false$, respectively. This explains the entries in column 5. 

\begin{figwindow}[0,r,%
\hspace*{3mm}
\scalebox{1.0}
{
\begin{tikzpicture}[description/.style={fill=white,inner sep=2pt}]
\tikzstyle{treenode} = [anchor=west, minimum width=1.5cm]
\def\rectDist{0.05}

\def\nodesep{0.8}
\def\innersep{10}

\node[treenode] (S1) at (0, 3 * \nodesep) {$(0,$};
\node[treenode] (B1) at (1, 3 * \nodesep) {$\infty]$};
\draw [dashed, rounded corners=1.5ex] (0.3,0.8 + 2 * \nodesep) -- (0.75,1.15 + 2 * \nodesep) -- (2.2,0.0 +2 *  \nodesep) --
(1.75,-0.35 + 2 * \nodesep) -- cycle; 

\node[treenode] (S2) at (0, 2 * \nodesep) {$(0,$};
\node[treenode] (B2) at (1, 2 * \nodesep) {$\infty]$};
\draw [dashed, rounded corners=1.5ex] (0.3,0.8 + \nodesep) -- (0.75,1.15 + \nodesep) -- (2.2,0.0 + \nodesep) --
(1.75,-0.35 + \nodesep) -- cycle; 

\node[treenode] (S3) at (0, 1 * \nodesep) {$(0,$};
\node[treenode] (B3) at (1, 1 * \nodesep) {$\infty]$};
\draw [dashed, rounded corners=1.5ex] (0.3,0.8) -- (0.75,1.15) -- (2.2,0.0) --
(1.75,-0.35) -- cycle; 

\node[treenode] (S4) at (0, 0) {$(-\infty,$};
\node[treenode] (B4) at (1, 0) {$0]$};

\draw (2.3, -0.4) -- (0,-0.4) -- (0,3 * \nodesep + 0.4) -- (2.3,3 * \nodesep + 0.4); 
\end{tikzpicture}}
%\begin{tabular}{|c}
%\hline
%$\threshold{0}{\infty}$\\
%$\ddots$\\ 
%$\threshold{0}{\infty}$\\
%$\ddots$\\ 
%$\threshold{0}{\infty}$\\
%$\ddots$\\ 
%$\threshold{-\infty}{0}$\\\hline
%\end{tabular}
\hspace*{3mm},
{A block}]
Next observe that column 5 has three blocks separated by horizontal
lines, two of which are non-empty. Consider the uppermost block
consisting of four intervals, and within it, the northwest-southeast
diagonals, as illustrated by the dashed shapes in the figure 
to the right. Each diagonal joins two
numbers, and we compute the difference between the upper left and the
lower right number for each diagonal, i.e., $0-\infty$, $0-\infty$, and $0-0$,
which give $-\infty$, $-\infty$, and $0$, respectively. Our theorem states that
$a_5$ must be chosen greater than any of those numbers, and thus in
particular greater than $0$. The theorem also states that $a_5$ must
be chosen less than any of the differences obtained by taking the
northeast-southwest diagonals, i.e.~$\infty-0,\infty-0,\infty--\infty$, which however only
says that $a_5<\infty$. In the same way, constraints on $a_5$ can be
collected from the lowermost block, in any case just stating that
$a_5>0$. We simply choose $a_5=1$.  
\end{figwindow}

Now, each node in column 4 with upper successor $\threshold{s_u}{b_u}$
and lower successor $\threshold{s_l}{b_l}$, 
is filled by the thresholds 
$\threshold{\max\{s_u,s_l+a_5\}}{\min\{b_u,b_l+a_5\}}$. 
E.g., the topmost $\threshold{1}{\infty}$ is 
$\threshold{\max\{0,0+a_5\}}{\min\{\infty,\infty+a_5\}}$. 

In the next step, we have to choose $a_4$ so that 
 \[
\begin{array}{l}
\max\{1-\infty,1-1,\quad 1-0,-\infty-0, \quad 0-0,-\infty-0,-\infty-0\}<a_4<\\
\min\{\infty-1,\infty-0,\quad \infty--\infty,0--\infty,\quad 1--\infty,0--\infty,0--\infty\}.
\end{array}
\]  
Choosing $a_4=2$ will do. Note that the bound $1-0<a_4$ comes from the
middle block of column 4 and thus ultimately from $x_3\lor x_4$. Our
algorithm enforces that $a_4>a_5$, which must hold for an LPB representing 
$x_3\lor x_4$.

In the next step, $a_3$ can also be
chosen to be any number $>1$ so we choose $2$ again. 
In the next step, $2<a_2<4$
must hold so we choose $a_2=3$. Finally, $3<a_1<5$ must hold so we choose
$a_1=4$. As result we obtain the LPB \linebreak 
$4x_1+3x_2+2x_3+2x_4+x_5\geq\threshold{4}{5}$.


\section{Experiments}\label{experiments-sec}

Both algorithms were implemented in C++.  For evaluation we used
more than 300,000 randomly generated DNFs known to be threshold
functions, for $m\leq 22$.

\begin{figwindow}[5,r,%
{\mbox{\hspace{0em}
\begin{tikzpicture}
\begin{semilogyaxis}[legend
  style={at={(0.53,0.95)}},width=7cm,%xlabel=dimension,%
%ylabel={Runtime ms, \#.~var.~occurr.},
ymax=10000000]
\addplot[mark=triangle] coordinates {
(4,0.1)
(5,0.1)
(6,0.1)
(7,0.1)
(8,0.128)
(9,0.3)
(10,0.4)
(11,0.6)
(12,1.0)
(13,1.9)
(14,3.2)
(15,6.0)
(16,11.0)
(17,29.2)
(18,48.6)
(19,111.3)
(20,178.8)
(21,645.4)
(22,1528.9)
}; 
%\addlegendentry{Combin.~alg.}%No repair necessary
\addplot[mark=star] coordinates {
(4,0.1)
(5,0.2)
(6,0.2)
(7,0.3)
(8,0.3)
(9,0.5)
(10,0.8)
(11,1.4)
(12,2.3)
(13,6.4)
(14,10.0)
(15,24.0)
(16,34.2)
(17,97.4)
(18,262.1)
(19,897.3)
(20,2178.2)
(21,12271.8)
(22,29291.5)
}; %\addlegendentry{LP alg.}
\addplot[mark=o] coordinates {
(4,7.04)
(5,13.08)
(6,24.39)
(7,45.34)
(8,69.64)
(9,179.11)
(10,293.07)
(11,550.51)
(12,871.7)
(13,1710.76)
(14,2667.24)
(15,5052.25)
(16,8039.12)
(17,16885.9)
(18,24264.3)
(19,46262.8)
(20,63234.13)
(21,181538)
(22,243303)
}; 
%\addlegendentry{Input size}%No repair necessary
\legend{
Comb.~alg.,
LP alg.,
Input size
};
\end{semilogyaxis}
% \begin{axis}...\end{axis} for normal plots,
% \begin{semilogxaxis}...\end{semilogxaxis} for plots which have a normal y axis and a logarithmic x axis,
% \begin{semilogyaxis}...\end{semilogyaxis} the same with x and y switched,
% \begin{loglogaxis}...\end{loglogaxis} for double–logarithmic plots.
\end{tikzpicture}}}
,%
{\label{runtime:fig}Runtime}] 
Figure \ref{runtime:fig} shows the runtime per problem 
for both algorithms in ms, as well as the problem size.
The x-axis shows $m$. The y-axis is in logarithmic scale. 
We observe that the combinatorial algorithm could solve problems up to
$m=22$ in a couple of seconds, while the LP algorithm appears to scale
worse and needs around 30 seconds for the biggest problems. 
%HERE 
Second, the runtime seems to be exponential in $m$. 
%Third, the
%combinatorial algorithm is considerably but not dramatically faster than the LP
%algorithm. 
Let us now discuss the problem size. Note that the input to our procedure is a
DNF. The combinatorics wants it that the size of the DNFs
grows exponentially in $m$.  
The size, around 243,000 for $m=22$, is shown in the
figure. The fact that the curve is almost a perfect straight line and appears to
be parallel to the curve for the runtime of the combinatorial
algorithm shows that the input size increases at the
same rate as that runtime, which means that the algorithm appears
to run in time linear to the input, whereas the LP algorithm
performs worse. 
%. Note the difference between  $O(m\cdot t)$ and
%the theoretical runtime $O(m^7t^5)$ for the LP algorithm. 
\end{figwindow}



%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliography{smaus,own_publications}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns

%\appendix
%Appendix A
%\balancecolumns % GM June 2007
% That's all folks!
\end{document}



%%% Local Variables:
%%% mode: latex
%%% x-symbol-8bits: t
%%% TeX-master: t
%%% coding: utf-8-unix
%%% End:
